package leet707designlinkedlist

// https://leetcode.cn/problems/design-linked-list/

// Design a singly linked list.
// Implement the MyLinkedList class:
// - MyLinkedList() Initializes the MyLinkedList object.
// - get(index) Get the value of the index-th node in the linked list. If the index is invalid, return -1.
// - addAtHead(val) Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
// - addAtTail(val) Append a node of value val as the last element of the linked list.
// - addAtIndex(index, val) Add a node of value val before the index-th node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.
// - deleteAtIndex(index) Delete the index-th node in the linked list, if the index is valid.
// Example 1:
// Input
// ["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
// [[[], [1], [3], [1, 2], [1], [0], [0]]]
// Output
// [null, null, null, null, 2, null, 3]
// Explanation
// MyLinkedList myLinkedList = new MyLinkedList();
// myLinkedList.addAtHead(1);    // linked list becomes 1
// myLinkedList.addAtTail(3);    // linked list becomes 1->3
// myLinkedList.addAtIndex(1, 2); // linked list becomes 1->2->3
// myLinkedList.get(1);          // returns 2
// myLinkedList.deleteAtIndex(0); // now the linked list is 2->3
// myLinkedList.get(0);          // returns 2
// Constraints
// 0 <= index, val <= 1000
// Please do not use the size of the linked list to determine the length.
// The number of calls to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex is at most 1000.
// The values of the linked list nodes are in the range [0, 1000].
type MyLinkedList struct {
	head *ListNode // head是第一个节点的引用，注意此处不是虚拟节点
	tail *ListNode // tail是最后一个节点的引用，注意此处不是虚拟节点
	size int // size表示链表的长度
}
type ListNode struct {
	Val  int
	Next *ListNode
	Prev *ListNode
}
// Constructor initializes the linked list.
func Constructor() MyLinkedList {
	return MyLinkedList{
		head: nil,
		tail: nil,
		size: 0,
	}
}
// Get the value of the index-th node in the linked list. If the index is invalid, return -1.
// If the index is valid, return the value of the node at that index.
// If the index is invalid, return -1.
// The index is 0-based, so the first node is at index 0.
// If the index is greater than or equal to the size of the linked list, return -1.
// If the index is less than 0, return -1.
func (this *MyLinkedList) Get(index int) int {
	if index < 0 || index >= this.size {
		return -1
	}
	// 此处有一个小技巧，如果index小于size/2，就从头节点开始遍历，否则从尾节点开始遍历
	// 这样可以减少遍历的时间复杂度
	if index < this.size/2 {
		current := this.head // 先指向头结点，从他的Next开始遍历所有的Next，用i计数，直到i等于index
		for i := 0; i < index; i++ {
			current = current.Next
		}
		return current.Val
	} else {
		current := this.tail
		for i := this.size - 1; i > index; i-- {
			current = current.Prev
		}
		return current.Val
	}
}
// Add a node of value val before the first element of the linked list.
// After the insertion, the new node will be the first node of the linked list.
func (this *MyLinkedList) AddAtHead(val int) {
	newNode := &ListNode{Val: val}
	if this.size == 0 {
		this.head = newNode
		this.tail = newNode
	} else {
		newNode.Next = this.head
		this.head.Prev = newNode
		this.head = newNode
	}
	this.size++
}
// Append a node of value val as the last element of the linked list.
func (this *MyLinkedList) AddAtTail(val int) {
	newNode := &ListNode{Val: val}
	if this.size == 0 {
		this.head = newNode
		this.tail = newNode
	} else {
		newNode.Prev = this.tail
		this.tail.Next = newNode
		this.tail = newNode
	}
	this.size++
}
// Add a node of value val before the index-th node in the linked list.
// If index equals the length of the linked list, the node will be appended to the end of the linked list.
// If index is greater than the length, the node will not be inserted.
// If index is less than 0, the node will not be inserted.
func (this *MyLinkedList) AddAtIndex(index int, val int) {
	if index < 0 || index > this.size {
		return
	}
	if index == 0 {
		this.AddAtHead(val)
	} else if index == this.size {
		this.AddAtTail(val)
	} else {
		newNode := &ListNode{Val: val}
		if index < this.size/2 {
			current := this.head
			for i := 0; i < index-1; i++ {
				current = current.Next
			}
			newNode.Next = current.Next
			newNode.Prev = current
			current.Next.Prev = newNode
			current.Next = newNode
		} else {
			current := this.tail
			for i := this.size - 1; i > index; i-- {
				current = current.Prev
			}
			newNode.Prev = current.Prev
			newNode.Next = current
			current.Prev.Next = newNode
			current.Prev = newNode
		}
		this.size++
	}
}
// Delete the index-th node in the linked list, if the index is valid.
// If the index is valid, delete the node at that index.
func (this *MyLinkedList) DeleteAtIndex(index int) {
	if index < 0 || index >= this.size {
		return
	}
	if index == 0 {
		this.head = this.head.Next
		if this.head != nil {
			this.head.Prev = nil
		} else {
			this.tail = nil
		}
	} else if index == this.size-1 {
		this.tail = this.tail.Prev
		this.tail.Next = nil
	} else {
		if index < this.size/2 {
			current := this.head
			for i := 0; i < index; i++ {
				current = current.Next
			}
			current.Prev.Next = current.Next
			current.Next.Prev = current.Prev
		} else {
			current := this.tail
			for i := this.size - 1; i > index; i-- {
				current = current.Prev
			}
			current.Prev.Next = current.Next
			current.Next.Prev = current.Prev
		}
	}
	this.size--
}
// Your MyLinkedList object will be instantiated and called as such:
// obj := Constructor();
// param_1 := obj.Get(index);
// obj.AddAtHead(val);
// obj.AddAtTail(val);
// obj.AddAtIndex(index,val);
// obj.DeleteAtIndex(index);
// fmt.Println(param_1)
// fmt.Println(obj)
// fmt.Println(obj.head)
// fmt.Println(obj.tail)
// fmt.Println(obj.size)
// fmt.Println(obj.Get(0))